import hashlib
import bisect


def _hash(key: str):
    """ hash 一个字符串 ，将一个字符产使用 utf-8 格式进行编码，然后获取结果的16进制摘要，最后将这个16进制数转换成10进制数"""
    return int(hashlib.md5(key.encode("utf-8")).hexdigest(), 16)  # hexdigest() 获取16进制数 int(xxx,16) 将一个16进制数转换成10进制数


class ConsistentHashRing:
    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas
        self.ring = dict()
        self._sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)

    def add_node(self, node):
        for i in range(self.replicas):
            virtual_node = f"{node}#{i}"
            key = _hash(virtual_node)
            self.ring[key] = node
            bisect.insort(self._sorted_keys, key)

    def remove_node(self, node):
        for i in range(self.replicas):
            virtual_node = f"{node}#{i}"
            key = _hash(virtual_node)
            if key in self.ring:
                del self.ring[key]
                self._sorted_keys.remove(key)

    def get_node(self, key_str: str):
        if not self.ring:
            return None
        key = _hash(key_str)
        index = bisect.bisect(self._sorted_keys, key)
        if index == len(self._sorted_keys):
            return 0
        return self.ring[self._sorted_keys[index]]


consistent_hash_ring = ConsistentHashRing(["node1", "node2", "node3"], replicas=100)
node_info_1 = consistent_hash_ring.get_node("test123")
node_info_2 = consistent_hash_ring.get_node("test456")
print(node_info_1)
print(node_info_2)

print("__________________________________")
consistent_hash_ring.remove_node("node2")
node_info_1 = consistent_hash_ring.get_node("test123")
node_info_2 = consistent_hash_ring.get_node("test456")
print(node_info_1)
print(node_info_2)


"""
result:
node3
node2
__________________________________
node3
node1
"""
